package learn.sort.marge;

import learn.CommUtil;

import java.util.Arrays;

/**
 * 归并排序(非递归方法)
 */
public class MargeSort2 {

    public static void main(String[] args) {
        int[] arr = CommUtil.arr(100);
        int[] old = Arrays.copyOf(arr, arr.length);
//        int[] arr = {69, 26};
        CommUtil.printArray("原数组: ", arr);
        process(arr);
        CommUtil.printArray("排序后: ", arr);


        Arrays.sort(old);
        CommUtil.check(old, arr);
    }


    public static void process(int[] arr) {
        int margeSize = 1;
        int len = arr.length;
        while (margeSize <= len) {
            int l = 0;
            while (l < len) {
                int m = l + margeSize - 1;
                if (m >= len - 1) {
                    break;
                }
                int r = Math.min(m + margeSize, len - 1);
                marge(arr, l, m, r);
                l = r + 1;
            }
            if (margeSize > len / 2) {
                break;
            }
            margeSize <<= 1;
        }
    }

    private static void marge(int[] arr, int l, int m, int r) {

        int[] help = new int[r - l + 1];
        int l1 = l;
        int l2 = m + 1;
        int i = 0;

        while (l1 <= m && l2 <= r) {
            help[i++] = arr[l1] <= arr[l2] ? arr[l1++] : arr[l2++];
        }
        while (l1 <= m) {
            help[i++] = arr[l1++];
        }
        while (l2 <= r) {
            help[i++] = arr[l2++];
        }
        // 修改原数组
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }

    }


}


